package edu.fpa.day0719;

public class Test06<K,V> {
    Node2[] table;  //位桶数组，bucket array
    int size;      //存放键值对的个数

    public Test06() {
        table = new Node2[16];   //长度一般定义为2的整数幂
    }

    public V get(K key) {
        int hash = myHash(key.hashCode(), table.length);
        V value = null;

        if(table[hash]!=null) {
            Node2 temp = table[hash];

            while(temp!=null) {
                if(temp.key.equals(key)) {  //如果相等，则说明找到了键值对，返回相应的value
                    value = (V)temp.value;
                    break;
                }else {
                    temp = temp.next;
                }
            }
        }

        return value;
    }

    public void put(K key,V value) {
        //如果要完善，还需要考虑数组扩容的问题！！！在ArrayList中有相应的解决方法

        //定义了新的节点对象
        Node2 newNode2 = new Node2();
        newNode2.hash = myHash(key.hashCode(), table.length);
        newNode2.key = key;
        newNode2.value = value;
        newNode2.next = null;

        Node2 temp = table[newNode2.hash];
        Node2 iterLast = null;  //正在遍历最后一个元素
        boolean keyRepeat = false;

        if(temp == null) {
            //此处数组元素为空，则直接将新节点放进去
            table[newNode2.hash] = newNode2;
            size++;
        }else {
            //此处数组元素不为空，则遍历对应链表
            while(temp!=null) {
                //判断key如果重复，则覆盖
                if(temp.key.equals(key)) {
                    keyRepeat = true;
                    temp.value = value;  //只需要覆盖value即可，其他的值（hash，key，next）保持不变
                    break;
                }else {
                    //key不重复,则遍历下一个
                    iterLast = temp;
                    temp = temp.next;
                }
            }

            if(!keyRepeat) {  //没有发生key重复的情况，则添加到链表最后
                iterLast.next = newNode2;
                size++;
            }
        }
    }

    @Override
    public String toString() {
        //(10:l,20:y)
        StringBuilder sb = new StringBuilder("{");

        //遍历链表
        for(int i=0;i<table.length;i++) {
            Node2 temp = table[i];

            while(temp!=null) {
                sb.append(temp.key+":"+temp.value+",");
                temp = temp.next;
            }
        }
        sb.setCharAt(sb.length()-1, '}');
        return sb.toString();
    }

    public static void main(String[] args) {
        Test06<Integer,String> num = new Test06<>();
        num.put(10, "l");
        num.put(20, "y");

        System.out.println(num.get(10));

    }


    public static int myHash(int h,int length) {
//		System.out.println("hash in myHash"+(h&(length-1)));  //直接位运算，效率高
//		System.out.println("hash in myHash"+(h%(length-1)));  //取模运算，效率低
        return h&(length-1);
    }
}
